package week02

// 355. 设计推特
// https://leetcode-cn.com/problems/design-twitter/

var sendTime = 0	// 模拟发文时间

type Twitter struct {
	followList map[int]map[int]struct{}     // 关注列表
	tweetList map[int][]*Tweer              // 推文列表
}


/** Initialize your data structure here. */
func Constructor() Twitter {
	return Twitter{
		followList: make(map[int]map[int]struct{}),
		tweetList: make(map[int][]*Tweer),
	}
}


/** Compose a new tweet. */
func (this *Twitter) PostTweet(userId int, tweetId int)  {
	this.tweetList[userId] = append(this.tweetList[userId], newTweer(tweetId))
}


/** Retrieve the 10 most recent tweet ids in the user's news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent. */
func (this *Twitter) GetNewsFeed(userId int) []int {
	heap := &BinaryHeap{}
	// 自己的推文(只入堆10条)
	twl := this.getUserTweer(userId, 10)
	for _, tw := range twl {
		heap.push(tw)
	}
	// 关注的用户
	fl, ok := this.followList[userId]
	if ok {
		for fid := range fl {
			twl := this.getUserTweer(fid, 10)
			for _, tw := range twl {
				heap.push(tw)
			}
		}
	}
	var ans []int
	for i := 0; i < 10 && !heap.empty(); i++ {
		tw := heap.pop()
		ans = append(ans, tw.id)
	}
	return ans
}

// 获取用户count数量推文
func (this *Twitter) getUserTweer(userId, count int) []*Tweer {
	var ans []*Tweer
	twl := this.tweetList[userId]
	for i := len(twl)-1; i >= 0 && count > 0; i-- {
		ans = append(ans, twl[i])
		count--
	}
	return ans
}


/** Follower follows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Follow(followerId int, followeeId int)  {
	set, ok := this.followList[followerId]
	if !ok {
		set = make(map[int]struct{})
	}
	set[followeeId] = struct{}{}
	this.followList[followerId] = set
}


/** Follower unfollows a followee. If the operation is invalid, it should be a no-op. */
func (this *Twitter) Unfollow(followerId int, followeeId int)  {
	if set, ok := this.followList[followerId]; ok {
		delete(set, followeeId)
	}
}

func newTweer(id int) *Tweer {
	sendTime++
	return &Tweer{
		id: id,
		time: sendTime,
	}
}

// 推文
type Tweer struct {
	id int
	time int    // 发文时间
}

// 二叉堆  大顶堆
type BinaryHeap struct {
	list []*Tweer
}

func (heap *BinaryHeap) push(tweer *Tweer) {
	heap.list = append(heap.list, tweer)
	// 调整堆
	var cur = len(heap.list) - 1
	var parent = (cur - 1) / 2
	for parent >= 0 {
		if heap.list[parent].time < heap.list[cur].time {
			heap.list[parent], heap.list[cur] = heap.list[cur], heap.list[parent]
			cur = parent
			parent = (cur - 1) / 2
		} else {
			break
		}
	}
}

func (heap *BinaryHeap) pop() *Tweer {
	var tweetId = heap.list[0]
	heap.list[0] = heap.list[len(heap.list)-1]
	heap.list = heap.list[:len(heap.list)-1]
	// 调整堆
	var cur = 0
	var child = cur * 2 + 1
	for child < len(heap.list) {
		var other = cur * 2 + 2
		if other < len(heap.list) && heap.list[child].time < heap.list[other].time {
			child = other
		}
		if heap.list[cur].time < heap.list[child].time {
			heap.list[cur], heap.list[child] = heap.list[child], heap.list[cur]
			cur = child
			child = cur * 2 + 1
		} else {
			break
		}
	}
	return tweetId
}

func (heap *BinaryHeap) empty() bool {
	return len(heap.list) == 0
}
